The invention relates to the field of telecommunications, more precisely to ARQ actions taken in the data layer (DLC) and is related to existing features proposed in HiperLan/2 standardization.
Vocabulary
HiperLan/2 is a standard for high-speed wireless LAN network developed by the European Telecommunications Standards Institute (ETSI). It operates in the 5 GHz frequency band at a data rate up to 54 Mbit/sec. It provides high-speed and short distance connections for the office and factory environment without wired connections. Its range may be enhanced through use of active forwarding nodes. HiperLan/2 is a private system owned and operated by the user. It is an extension or replacement for fixed LANs and is primarily used indoors but it is not inherently limited to that use.
The LAN networks use digital signals to convey data. Digital messages have to contend with errors in transmission. Error control provides the means to protect transmitted data from errors. Even physical links cannot guarantee that all bits will be transferred without errors. In a communication network it is the responsibility of the error control algorithm to detect those errors and in some cases correct them to support an error free link to upper layers.
Two error control strategies have been popular. One is Forward Error Correction (FEC) that uses error correction alone. The other is Automatic Repeat Request (ARQ) that uses error detection combined with retransmission of corrupted data. The latter is preferred primarily because it uses fewer overhead bits to detect errors than to correct the error. The following algorithms are used to implement FEC and ARQ.
Cyclic Redundancy Check (CRC) is a very powerful but easily implemented technique to obtain data reliability by protecting blocks of data called Frames. The transmitter appends an extra n-bit sequence to every frame called Frame Check Sequence (FCS). The FCS holds redundant information about the Frame that helps the transmitter to detect errors in the Frame.
Computing Parity involves counting the number of ones in the unit of data, and adding a zero or one to make the count odd or even depending on whether odd or even parity is used. An example is a 4-bit unit of data of 1001. For even parity a zero is added to the unit resulting in 10010 for an even number of bits. For odd parity a 1 is added. The result is 10011 for an odd number of bits. Computing parity that is even involves XORing the bits of the data stream together. Computing odd parity XORs the bits and negates the result equivalent to XNOR (xcx9c). The computations are as follows: Even: 1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}1=0; Odd: xcx9c(1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}1)=1. This system detects single bit errors. If one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data.
As an example, using the above system assuming even parity, A sends a data unit 10010 and B receives 11010. B computes the parity as 1{circumflex over ( )}1{circumflex over ( )}0{circumflex over ( )}1{circumflex over ( )}=1. Since the parity bits do not match (even parity the XOR result should be 0), there is an error. Rather than computing parity on the data bits and comparing them to the parity bit, the receiver will actually XOR the data bits and the parity bit. If the result is zero the data unit passes. If a 1 results there is an error. The parity generation function is expressed as P(d1,d2,d3, . . . dn)=P and P(d1,d2,d3 . . . dn,P)=0 if no error occurs. Since there is no indication of which bit is flipped there is no way to correct it.
Unfortunately, if two bits are flipped, A sends 10010 and B receives 11000 and B computes parity as 1{circumflex over ( )}1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}=0. The result shows no error. Therefore, to use this system you must assume a low probability of two errors in one data unit.
Another error checking procedure is Parallel Parity that is based on regular parity. It can detect whether or not there was an error and which bit is flipped. This method is implemented on a block of data that is made of sum words. Referring to FIG. 1, the parity is then added to the columns and rows. Every row has bit parity. If one block is flipped, the result is two parity errors, one in the rows and one in the column""s parity. The intersection of the row and column of the flipped bit identifies the error.
Yet another way to check for errors is Check Sum. It uses modulo summation to detect errors in a stream of data. The sum operation is operated on a package of bytes where the last byte is the Check Sum number. When you add all the numbers in the package the sum should be zero. In octets the addition is modulo 256. If the sum reaches 256 it turns to zero. If it doesn""t we know that there is an error. It cannot correct for errors. In the example of FIG. 2 there are blocks of octets represented in the Hexadecimal. The last number in every row is a summation. If there is no error it is zero
The invention pertains to adaptive allocation of ARQ feedback bandwidth to conserve bandwidth. The data stream scheduler is informed of the status of a PDU to be retransmitted at the receiver to allow adaptive scheduling of ARQ feedback bandwidth during data transmission. Information about the receiver is provided in the ARQ feedback PDU that may be the ABIR flag. This allows the receiver to adjust the bandwidth to meet the need to supply enough bandwidth for message retransmission traffic.
A platform for implementing the invention is the HIPERLAN/2 protocol developed by the European Telecommunications Standards Institute (ETSI). In the ARQ protocol of HIPERLAN/2, data PDUs are selectively acknowledged by using an ARQ feedback message. Such an ARQ feedback message contains three bitmaps with eight bits each. The receiver and transmitter windows are divided into blocks each the same size as a bitmap. The bitmaps can be shifted over the window so that a bit therein belongs to a particular data PDU. If a bit is set to 1, the assigned data PDU is acknowledged. If the bit is set to zero the assigned PDU has to be retransmitted.
A data PDU consists of a 48-byte payload field. The number of acknowledged data PDUs is limited per ARQ feedback message resulting in variance in the number of feedback messages. In the HIPERLAN/2 protocol, the scheduler is responsible for granting transmission capacity for the ARQ feedback messages. A robust scheduling algorithm adapts the feedback bandwidth to the current transmission rate. The transmission rate of ARQ feedback messages depends on factors such as negotiated window size, round trip time and fading behavior of the physical indoor channel that results in burst errors.
In the HiperLAN/2 protocol the receiver of data PDUs (i.e. the transmitter of ARQ feedback messages) may request an increase in the ARQ signaling bandwidth. One bit is available for the request that is the ABIR. The state of the ABIR bit determines the need for bandwidth. A null indicates no need for more bandwidth and 1 indicates the need for more bandwidth. This implementation eliminates the need for a sophisticated scheduler algorithm
Accordingly, it is an object of the Invention to preserve bandwidth when missing data units are retransmitted to a bitmap.
It is another object of the invention to decrease the number of retransmissions of data units missing from a bitmap.
It is yet another object of this invention to eliminate the need for algorithms to detect the errors in data units.